package test;

class BinarySortTree {
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }

    public void add(Node node) {
        if (root == null) {
            //如果root为空则直接让root指向node
            root = node;
        } else {
            root.add(node);
        }
    }

    //前序遍历
    public void preOrder() {
        if (root == null) {
            System.out.println("数为空，不能遍历");
        } else {
            root.preOrder();
        }
    }

    //中序遍历
    public void midOrder() {
        if (root == null) {
            System.out.println("树为空，不能遍历");
        } else {
            root.midOrder();
        }

    }

    //后序遍历
    public void laterOrder() {
        if (root == null) {
            System.out.println("树为空，不能遍历");
        } else {
            root.laterOrder();
        }
    }

    //查找要删除的节点
    public Node searchNode(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchNode(value);
        }
    }

    //查找要删除的节点的父节点
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchparent(value);
        }
    }
    //编写方法：
    //返回的以node为根节点的二叉排序树的最小节点的值
    //删除node为根节点的二叉排序树的最小节点

    //node 传入的节点（当作二叉排序树的根节点）
    //返回的是以nide为根节点的二叉排序树的最小节点的值
    public int delChildRightTreeMin(Node node) {
        Node target = node;
        //循环的查找左节点，就会摘到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这时target就指向了最小节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }

    //删除左边最大的节点并返回值
    public int delChildLeftTreeMax(Node node) {
        Node target = node;
        while (target.right != null) {
            target = target.right;
        }
        delNode(target.value);
        return target.value;
    }


    //删除节点
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //先去找到需要删除的节点
            Node targetNode = searchNode(value);
            if (targetNode == null) {
                return;
            }
            //如果我们发现这颗二叉排序树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
            }
            //去找到targetNode的父节点
            Node parent = searchParent(value);
            if (targetNode.left == null && targetNode.right == null) {//说明这个节点是叶子节点
                //判断targetNode是父节点的左子节点还是右子节点
                if (parent.left != null && parent.left.value == value) {//说明是左子节点
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {//说明是右子节点
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) {//删除有两颗子树的节点
                //传入需要插入的节点的右节点
                int minVal = delChildRightTreeMin(targetNode.right);
                targetNode.value = minVal;
//                int maxVal = delChildLeftTreeMax(targetNode.left);
//                targetNode.value = maxVal;
            } else {//删除只有一颗子树的节点//如果删除的节点由左子树
                if (targetNode.left != null) {
                    //如果targetNode是parent的左子节点
                    if (parent != null) {
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {//targetNode是parent的右子节点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {//要删除的节点有右子节点
                    if (parent.left.value == value) {
                        parent.left = targetNode.right;
                    } else {
                        parent.right = targetNode.right;
                    }
                }
            }
        }
    }
}
